// PART OF THE MACHINE SIMULATION. DO NOT CHANGE.

package nachos.machine;

import nachos.security.*;

/**
 * Process 类模拟支持 R3000 指令集子集的 MIPS 处理器
 * 具体来说，Process 缺少所有协处理器支持，只能在用户模式下执行。
 * 地址转换信息通过 API 访问
 * API 还允许内核设置异常处理程序，以便在任何用户模式异常时调用
 *
 * <p>
 * Process 的 API 是可重入的，因此单个模拟处理器可以由多个用户线程共享
 *
 * <p>
 * Process 的实例还包括用户程序可访问的物理内存页，其大小由构造函数固定
 */
public final class Processor {
    /**
     * 分配具有指定内存量的新 MIPS 处理器
     *
     * @param privilege    封装对 Nachos 机器的特权访问
     * @param numPhysPages 要附加的物理内存的页数
     */
    public Processor(Privilege privilege, int numPhysPages) {
        System.out.print(" processor");

        this.privilege = privilege;
        privilege.processor = new ProcessorPrivilege();

        Class clsKernel = Lib.loadClass(Config.getString("Kernel.kernel"));
        Class clsVMKernel = Lib.tryLoadClass("nachos.vm.VMKernel");

        usingTLB =
                (clsVMKernel != null && clsVMKernel.isAssignableFrom(clsKernel));

        // 创建物理内存
        this.numPhysPages = numPhysPages;
        for (int i = 0; i < numUserRegisters; i++)
            registers[i] = 0;
        mainMemory = new byte[pageSize * numPhysPages];

        // 如果使用 TLB，translations 则代表着 TLB，否则代表着页表
        // 应该注意，在上下文切换时，TLB 应该设为无效，页表应该换成另一个线程的页表
        if (usingTLB) {
            translations = new TranslationEntry[tlbSize];
            for (int i = 0; i < tlbSize; i++)
                translations[i] = new TranslationEntry();
        } else {
            // 虽然在这里会设置为 null
            // 但是在UserProcess 中会将 translations 设置为自己的页表
            translations = null;
        }
    }

    /**
     * 设置异常处理程序，每当发生用户异常时调用
     *
     * <p>
     * 调用异常处理程序时，将启用中断，CPU 原因寄存器将指定异常的原因（请参阅 exception* 常量）
     *
     * @param exceptionHandler 内核异常处理程序
     */
    public void setExceptionHandler(Runnable exceptionHandler) {
        this.exceptionHandler = exceptionHandler;
    }

    /**
     * 获取异常处理程序，该异常处理程序由上次调用 setExceptionHandler() 设置
     *
     * @return 异常处理程序
     */
    public Runnable getExceptionHandler() {
        return exceptionHandler;
    }

    /**
     * 在当前 PC 上开始执行指令。不会返回
     */
    public void run() {
        Lib.debug(dbgProcessor, "starting program in current thread");

        // 模拟 pc = pc + 1 的硬件过程，代码中 +4 是因为一个指令 4 个字节
        registers[regNextPC] = registers[regPC] + 4;

        Machine.autoGrader().runProcessor(privilege);

        Instruction inst = new Instruction();

        // 循环中执行每一条指令（取指令、解析指令、执行指令）
        while (true) {
            try {
                inst.run();
            } catch (MipsException e) {
                e.handle();
            }

            // 每次执行完 instruction 调用 tick()
            privilege.interrupt.tick(false);
        }
    }

    /**
     * 读取并返回指定 CPU 寄存器的内容
     *
     * @param number 要读取的寄存器
     * @return 寄存器的值
     */
    public int readRegister(int number) {
        Lib.assertTrue(number >= 0 && number < numUserRegisters);

        return registers[number];
    }

    /**
     * 将指定的值写入指定的 CPU 寄存器
     *
     * @param number 要写的寄存器
     * @param value  要写入的值
     */
    public void writeRegister(int number, int value) {
        Lib.assertTrue(number >= 0 && number < numUserRegisters);

        if (number != 0)
            registers[number] = value;
    }

    /**
     * 测试此处理器是使用软件管理的 TLB，还是使用单级分页
     *
     * <p>
     * 如果值为 false，则该处理器直接支持单级分页
     * 使用 setPageTable()
     *
     * <p>
     * 如果值为 true，则此处理器具有软件管理的TLB
     * 使用 gettlsize() readTLBEntry() 和 writelbentry()
     *
     * <p>
     * 使用与错误地址转换机制关联的方法将导致断言失败
     *
     * @return true 如果此处理器具有软件管理的TLB
     */
    public boolean hasTLB() {
        return usingTLB;
    }

    /**
     * 获取当前页表，它由上次调用 setPageTable() 调用的
     *
     * @return 当前页表
     */
    public TranslationEntry[] getPageTable() {
        Lib.assertTrue(!usingTLB);

        return translations;
    }

    /**
     * 设置页表指针
     * 所有进一步的地址转换将使用指定的页表
     * 当前地址空间的大小将根据页表数组的长度确定
     *
     * @param pageTable 要使用的页表
     */
    public void setPageTable(TranslationEntry[] pageTable) {
        Lib.assertTrue(!usingTLB);

        this.translations = pageTable;
    }

    /**
     * 返回此处理器 TLB 中的条目数
     *
     * @return 此处理器 TLB 中的条目数
     */
    public int getTLBSize() {
        Lib.assertTrue(usingTLB);

        return tlbSize;
    }

    /**
     * 返回指定的 TLB 项
     *
     * @param number TLB 的索引
     * @return 指定 TLB 条目的内容
     */
    public TranslationEntry readTLBEntry(int number) {
        Lib.assertTrue(usingTLB);
        Lib.assertTrue(number >= 0 && number < tlbSize);

        return new TranslationEntry(translations[number]);
    }

    /**
     * 填写指定的 TLB 条目
     *
     * <p>
     * TLB 是完全关联的，因此条目在 TLB 中的位置不会影响任何内容
     *
     * @param number TLB 的索引
     * @param entry  TLB 条目的新内容
     */
    public void writeTLBEntry(int number, TranslationEntry entry) {
        Lib.assertTrue(usingTLB);
        Lib.assertTrue(number >= 0 && number < tlbSize);

        translations[number] = new TranslationEntry(entry);
    }

    /**
     * 返回连接到此模拟处理器的物理内存页数
     *
     * @return 物理内存的页数
     */
    public int getNumPhysPages() {
        return numPhysPages;
    }

    /**
     * 返回对物理内存数组的引用
     * 此数组的大小为 pageSize * getNumPhysPages()
     *
     * @return 主内存数组
     */
    public byte[] getMemory() {
        return mainMemory;
    }

    /**
     * 将页码和偏移量连接到地址中
     *
     * @param page   页码，必须介于 0 和 2 ^ 32 / pageSize - 1 之间
     * @param offset 页面内的偏移量，必须介于 0 和 pageSize - 1 之间
     * @return 由指定页和偏移量组成的 32 位地址
     */
    public static int makeAddress(int page, int offset) {
        Lib.assertTrue(page >= 0 && page < maxPages);
        Lib.assertTrue(offset >= 0 && offset < pageSize);

        return (page * pageSize) | offset;
    }

    /**
     * 从 32 位地址提取页码组成部分
     *
     * @param address 32 位地址
     * @return 地址的页码组成部分
     */
    public static int pageFromAddress(int address) {
        return (int) (((long) address & 0xFFFFFFFFL) / pageSize);
    }

    /**
     * 从地址中提取偏移量组成部分
     *
     * @param address 32 位地址
     * @return 地址的偏移量组成部分
     */
    public static int offsetFromAddress(int address) {
        return (int) (((long) address & 0xFFFFFFFFL) % pageSize);
    }

    private void finishLoad() {
        delayedLoad(0, 0, 0);
    }

    /**
     * 使用页表或 TLB 将虚拟地址转换为物理地址
     * 检查对齐情况，确保虚拟页有效，确保未写入只读页，确保生成的物理页有效，然后返回生成的物理地址
     *
     * @param vaddr   要转换的虚拟地址
     * @param size    内存引用的大小（必须为1、2 或 4）
     * @param writing true 如果内存引用是写入
     * @return 物理地址
     * @throws MipsException 如果发生转换错误
     */
    private int translate(int vaddr, int size, boolean writing)
            throws MipsException {
        // 各种检测
        if (Lib.test(dbgProcessor))
            System.out.println("\ttranslate vaddr=0x" + Lib.toHexString(vaddr)
                    + (writing ? ", write" : ", read..."));

        // check alignment
        if ((vaddr & (size - 1)) != 0) {
            Lib.debug(dbgProcessor, "\t\talignment error");
            throw new MipsException(exceptionAddressError, vaddr);
        }

        // 计算虚拟页以及页偏移
        int vpn = pageFromAddress(vaddr);
        int offset = offsetFromAddress(vaddr);

        TranslationEntry entry = null;

        // 如果不使用 TLB，translations 是页表，则找出对应的页然后找出物理帧
        if (!usingTLB) {
            if (translations == null || vpn >= translations.length ||
                    translations[vpn] == null ||
                    !translations[vpn].valid) {
                privilege.stats.numPageFaults++;
                Lib.debug(dbgProcessor, "\t\tpage fault");
                throw new MipsException(exceptionPageFault, vaddr);
            }

            entry = translations[vpn];
        }
        // 若使用 TLB，translations 是 TLB，遍历 TLB 找出符合的页
        else {
            for (int i = 0; i < tlbSize; i++) {
                if (translations[i].valid && translations[i].vpn == vpn) {
                    entry = translations[i];
                    break;
                }
            }
            if (entry == null) {
                privilege.stats.numTLBMisses++;
                Lib.debug(dbgProcessor, "\t\tTLB miss");
                throw new MipsException(exceptionTLBMiss, vaddr);
            }
        }

        // 检查是否尝试写入只读页
        if (entry.readOnly && writing) {
            Lib.debug(dbgProcessor, "\t\tread-only exception");
            throw new MipsException(exceptionReadOnly, vaddr);
        }

        // 检查物理页码是否超出范围
        int ppn = entry.ppn;
        if (ppn < 0 || ppn >= numPhysPages) {
            Lib.debug(dbgProcessor, "\t\tbad ppn");
            throw new MipsException(exceptionBusError, vaddr);
        }

        // 根据需要设置已用位和脏位
        entry.used = true;
        if (writing)
            entry.dirty = true;

        int paddr = (ppn * pageSize) + offset;

        if (Lib.test(dbgProcessor))
            System.out.println("\t\tpaddr=0x" + Lib.toHexString(paddr));
        return paddr;
    }

    /**
     * 在 vaddr 读取 size（1、2 或 4）字节的虚拟内存，并返回结果
     *
     * @param vaddr 要从中读取的虚拟地址
     * @param size  要读取的字节数（1、2 或 4）
     * @return 读取的值
     * @throws MipsException 如果发生转换错误
     */
    private int readMem(int vaddr, int size) throws MipsException {
        if (Lib.test(dbgProcessor))
            System.out.println("\treadMem vaddr=0x" + Lib.toHexString(vaddr)
                    + ", size=" + size);

        Lib.assertTrue(size == 1 || size == 2 || size == 4);

        int value = Lib.bytesToInt(mainMemory, translate(vaddr, size, false),
                size);

        if (Lib.test(dbgProcessor))
            System.out.println("\t\tvalue read=0x" +
                    Lib.toHexString(value, size * 2));

        return value;
    }

    /**
     * 从 vaddr 开始，将 value 写入 size（1、2 或 4）字节的虚拟内存
     *
     * @param vaddr 要写入的虚拟地址
     * @param size  要写入的字节数（1、2 或 4）
     * @param value 要存储的值
     * @throws MipsException 如果发生转换错误
     */
    private void writeMem(int vaddr, int size, int value)
            throws MipsException {
        if (Lib.test(dbgProcessor))
            System.out.println("\twriteMem vaddr=0x" + Lib.toHexString(vaddr)
                    + ", size=" + size + ", value=0x"
                    + Lib.toHexString(value, size * 2));

        Lib.assertTrue(size == 1 || size == 2 || size == 4);

        Lib.bytesFromInt(mainMemory, translate(vaddr, size, true), size,
                value);
    }

    /**
     * 完成正在进行的延迟加载并计划新加载
     *
     * @param nextLoadTarget 新加载的目标寄存器
     * @param nextLoadValue  要加载到新目标中的值
     * @param nextLoadMask   指定要覆盖新目标中的哪些位的掩码，如果 nextLoadMask 中的一位为 0
     *                       则寄存器 nextLoadTarget 的相应位将不会被写入
     */
    private void delayedLoad(int nextLoadTarget, int nextLoadValue,
                             int nextLoadMask) {
        // complete previous delayed load, if not modifying r0
        if (loadTarget != 0) {
            int savedBits = registers[loadTarget] & ~loadMask;
            int newBits = loadValue & loadMask;
            registers[loadTarget] = savedBits | newBits;
        }

        // schedule next load
        loadTarget = nextLoadTarget;
        loadValue = nextLoadValue;
        loadMask = nextLoadMask;
    }

    /**
     * 将 PC 前进到下一条指令
     *
     * <p>
     * 将 nextPC 寄存器的内容传输到 PC 寄存器中，然后将 4 添加到 nextPC 寄存器中的值
     * 与 advancePC(readRegister(regNextPC)+4) 相同
     *
     * <p>
     * 在处理系统调用异常后使用，以便处理器继续执行下一条指令
     */
    public void advancePC() {
        advancePC(registers[regNextPC] + 4);
    }

    /**
     * 将 nextPC 寄存器的内容传输到 PC 寄存器，然后写入 nextPC 寄存器
     *
     * @param nextPC nextPC 寄存器的新值
     */
    private void advancePC(int nextPC) {
        registers[regPC] = registers[regNextPC];
        registers[regNextPC] = nextPC;
    }

    /**
     * Caused by a syscall instruction.
     */
    public static final int exceptionSyscall = 0;
    /**
     * Caused by an access to an invalid virtual page.
     */
    public static final int exceptionPageFault = 1;
    /**
     * Caused by an access to a virtual page not mapped by any TLB entry.
     */
    public static final int exceptionTLBMiss = 2;
    /**
     * Caused by a write access to a read-only virtual page.
     */
    public static final int exceptionReadOnly = 3;
    /**
     * Caused by an access to an invalid physical page.
     */
    public static final int exceptionBusError = 4;
    /**
     * Caused by an access to a misaligned virtual address.
     */
    public static final int exceptionAddressError = 5;
    /**
     * Caused by an overflow by a signed operation.
     */
    public static final int exceptionOverflow = 6;
    /**
     * Caused by an attempt to execute an illegal instruction.
     */
    public static final int exceptionIllegalInstruction = 7;

    /**
     * The names of the CPU exceptions.
     */
    public static final String exceptionNames[] = {
            "syscall      ",
            "page fault   ",
            "TLB miss     ",
            "read-only    ",
            "bus error    ",
            "address error",
            "overflow     ",
            "illegal inst "
    };

    /**
     * Index of return value register 0.
     */
    public static final int regV0 = 2;
    /**
     * Index of return value register 1.
     */
    public static final int regV1 = 3;
    /**
     * Index of argument register 0.
     */
    public static final int regA0 = 4;
    /**
     * Index of argument register 1.
     */
    public static final int regA1 = 5;
    /**
     * Index of argument register 2.
     */
    public static final int regA2 = 6;
    /**
     * Index of argument register 3.
     */
    public static final int regA3 = 7;
    /**
     * Index of the stack pointer register.
     */
    public static final int regSP = 29;
    /**
     * Index of the return address register.
     */
    public static final int regRA = 31;
    /**
     * Index of the low register, used for multiplication and division.
     */
    public static final int regLo = 32;
    /**
     * Index of the high register, used for multiplication and division.
     */
    public static final int regHi = 33;
    /**
     * Index of the program counter register.
     */
    public static final int regPC = 34;
    /**
     * Index of the next program counter register.
     */
    public static final int regNextPC = 35;
    /**
     * Index of the exception cause register.
     */
    public static final int regCause = 36;
    /**
     * Index of the exception bad virtual address register.
     */
    public static final int regBadVAddr = 37;

    /**
     * The total number of software-accessible CPU registers.
     */
    public static final int numUserRegisters = 38;

    /**
     * Provides privilege to this processor.
     */
    private Privilege privilege;

    /**
     * MIPS registers accessible to the kernel.
     */
    private int registers[] = new int[numUserRegisters];

    /**
     * The registered target of the delayed load currently in progress.
     */
    private int loadTarget = 0;
    /**
     * The bits to be modified by the delayed load currently in progress.
     */
    private int loadMask;
    /**
     * The value to be loaded by the delayed load currently in progress.
     */
    private int loadValue;

    /**
     * <tt>true</tt> if using a software-managed TLB.
     */
    private boolean usingTLB;
    /**
     * Number of TLB entries.
     */
    private int tlbSize = 4;
    /**
     * Either an associative or direct-mapped set of translation entries,
     * depending on whether there is a TLB.
     */
    private TranslationEntry[] translations;

    /**
     * Size of a page, in bytes.
     */
    public static final int pageSize = 0x400;
    /**
     * Number of pages in a 32-bit address space.
     */
    public static final int maxPages = (int) (0x100000000L / pageSize);
    /**
     * Number of physical pages in memory.
     */
    private int numPhysPages;
    /**
     * Main memory for user programs.
     */
    private byte[] mainMemory;

    /**
     * The kernel exception handler, called on every user exception.
     */
    private Runnable exceptionHandler = null;

    private static final char dbgProcessor = 'p';
    private static final char dbgDisassemble = 'm';
    private static final char dbgFullDisassemble = 'M';

    private class ProcessorPrivilege implements Privilege.ProcessorPrivilege {
        public void flushPipe() {
            finishLoad();
        }
    }

    private class MipsException extends Exception {
        public MipsException(int cause) {
            Lib.assertTrue(cause >= 0 && cause < exceptionNames.length);

            this.cause = cause;
        }

        public MipsException(int cause, int badVAddr) {
            this(cause);

            hasBadVAddr = true;
            this.badVAddr = badVAddr;
        }

        public void handle() {
            writeRegister(regCause, cause);

            if (hasBadVAddr)
                writeRegister(regBadVAddr, badVAddr);

            if (Lib.test(dbgDisassemble) || Lib.test(dbgFullDisassemble))
                System.out.println("exception: " + exceptionNames[cause]);

            finishLoad();

            Lib.assertTrue(exceptionHandler != null);

            // autograder might not want kernel to know about this exception
            if (!Machine.autoGrader().exceptionHandler(privilege))
                return;

            exceptionHandler.run();
        }

        private boolean hasBadVAddr = false;
        private int cause, badVAddr;
    }

    private class Instruction {
        public void run() throws MipsException {
            fetch(); // 取指令
            decode(); // 解析
            execute(); // 执行指令
            writeBack();
        }

        private boolean test(int flag) {
            return Lib.test(flag, flags);
        }

        private void fetch() throws MipsException {
            if ((Lib.test(dbgDisassemble) && !Lib.test(dbgProcessor)) ||
                    Lib.test(dbgFullDisassemble))
                System.out.print("PC=0x" + Lib.toHexString(registers[regPC])
                        + "\t");

            value = readMem(registers[regPC], 4);
        }

        private void decode() {
            op = Lib.extract(value, 26, 6);
            rs = Lib.extract(value, 21, 5);
            rt = Lib.extract(value, 16, 5);
            rd = Lib.extract(value, 11, 5);
            sh = Lib.extract(value, 6, 5);
            func = Lib.extract(value, 0, 6);
            target = Lib.extract(value, 0, 26);
            imm = Lib.extend(value, 0, 16);

            Mips info;
            switch (op) {
                case 0:
                    info = Mips.specialtable[func];
                    break;
                case 1:
                    info = Mips.regimmtable[rt];
                    break;
                default:
                    info = Mips.optable[op];
                    break;
            }

            operation = info.operation;
            name = info.name;
            format = info.format;
            flags = info.flags;

            mask = 0xFFFFFFFF;
            branch = true;

            // get memory access size
            if (test(Mips.SIZEB))
                size = 1;
            else if (test(Mips.SIZEH))
                size = 2;
            else if (test(Mips.SIZEW))
                size = 4;
            else
                size = 0;

            // get nextPC
            nextPC = registers[regNextPC] + 4;

            // get dstReg
            if (test(Mips.DSTRA))
                dstReg = regRA;
            else if (format == Mips.IFMT)
                dstReg = rt;
            else if (format == Mips.RFMT)
                dstReg = rd;
            else
                dstReg = -1;

            // get jtarget
            if (format == Mips.RFMT)
                jtarget = registers[rs];
            else if (format == Mips.IFMT)
                jtarget = registers[regNextPC] + (imm << 2);
            else if (format == Mips.JFMT)
                jtarget = (registers[regNextPC] & 0xF0000000) | (target << 2);
            else
                jtarget = -1;

            // get imm
            if (test(Mips.UNSIGNED)) {
                imm &= 0xFFFF;
            }

            // get addr
            addr = registers[rs] + imm;

            // get src1
            if (test(Mips.SRC1SH))
                src1 = sh;
            else
                src1 = registers[rs];

            // get src2
            if (test(Mips.SRC2IMM))
                src2 = imm;
            else
                src2 = registers[rt];

            if (test(Mips.UNSIGNED)) {
                src1 &= 0xFFFFFFFFL;
                src2 &= 0xFFFFFFFFL;
            }

            if (Lib.test(dbgDisassemble) || Lib.test(dbgFullDisassemble))
                print();
        }

        private void print() {
            if (Lib.test(dbgDisassemble) && Lib.test(dbgProcessor) &&
                    !Lib.test(dbgFullDisassemble))
                System.out.print("PC=0x" + Lib.toHexString(registers[regPC])
                        + "\t");

            if (operation == Mips.INVALID) {
                System.out.print("invalid: op=" + Lib.toHexString(op, 2) +
                        " rs=" + Lib.toHexString(rs, 2) +
                        " rt=" + Lib.toHexString(rt, 2) +
                        " rd=" + Lib.toHexString(rd, 2) +
                        " sh=" + Lib.toHexString(sh, 2) +
                        " func=" + Lib.toHexString(func, 2) +
                        "\n");
                return;
            }

            int spaceIndex = name.indexOf(' ');
            Lib.assertTrue(spaceIndex != -1 && spaceIndex == name.lastIndexOf(' '));

            String instname = name.substring(0, spaceIndex);
            char[] args = name.substring(spaceIndex + 1).toCharArray();

            System.out.print(instname + "\t");

            int minCharsPrinted = 0, maxCharsPrinted = 0;

            for (int i = 0; i < args.length; i++) {
                switch (args[i]) {
                    case Mips.RS:
                        System.out.print("$" + rs);
                        minCharsPrinted += 2;
                        maxCharsPrinted += 3;

                        if (Lib.test(dbgFullDisassemble)) {
                            System.out.print("#0x" +
                                    Lib.toHexString(registers[rs]));
                            minCharsPrinted += 11;
                            maxCharsPrinted += 11;
                        }
                        break;
                    case Mips.RT:
                        System.out.print("$" + rt);
                        minCharsPrinted += 2;
                        maxCharsPrinted += 3;

                        if (Lib.test(dbgFullDisassemble) &&
                                (i != 0 || !test(Mips.DST)) &&
                                !test(Mips.DELAYEDLOAD)) {
                            System.out.print("#0x" +
                                    Lib.toHexString(registers[rt]));
                            minCharsPrinted += 11;
                            maxCharsPrinted += 11;
                        }
                        break;
                    case Mips.RETURNADDRESS:
                        if (rd == 31)
                            continue;
                    case Mips.RD:
                        System.out.print("$" + rd);
                        minCharsPrinted += 2;
                        maxCharsPrinted += 3;
                        break;
                    case Mips.IMM:
                        System.out.print(imm);
                        minCharsPrinted += 1;
                        maxCharsPrinted += 6;
                        break;
                    case Mips.SHIFTAMOUNT:
                        System.out.print(sh);
                        minCharsPrinted += 1;
                        maxCharsPrinted += 2;
                        break;
                    case Mips.ADDR:
                        System.out.print(imm + "($" + rs);
                        minCharsPrinted += 4;
                        maxCharsPrinted += 5;

                        if (Lib.test(dbgFullDisassemble)) {
                            System.out.print("#0x" +
                                    Lib.toHexString(registers[rs]));
                            minCharsPrinted += 11;
                            maxCharsPrinted += 11;
                        }

                        System.out.print(")");
                        break;
                    case Mips.TARGET:
                        System.out.print("0x" + Lib.toHexString(jtarget));
                        minCharsPrinted += 10;
                        maxCharsPrinted += 10;
                        break;
                    default:
                        Lib.assertTrue(false);
                }
                if (i + 1 < args.length) {
                    System.out.print(", ");
                    minCharsPrinted += 2;
                    maxCharsPrinted += 2;
                } else {
                    // most separation possible is tsi, 5+1+1=7,
                    // thankfully less than 8 (makes this possible)
                    Lib.assertTrue(maxCharsPrinted - minCharsPrinted < 8);
                    // longest string is stj, which is 40-42 chars w/ -d M;
                    // go for 48
                    while ((minCharsPrinted % 8) != 0) {
                        System.out.print(" ");
                        minCharsPrinted++;
                        maxCharsPrinted++;
                    }
                    while (minCharsPrinted < 48) {
                        System.out.print("\t");
                        minCharsPrinted += 8;
                    }
                }
            }

            if (Lib.test(dbgDisassemble) && Lib.test(dbgProcessor) &&
                    !Lib.test(dbgFullDisassemble))
                System.out.print("\n");
        }

        private void execute() throws MipsException {
            int value;
            int preserved;

            // 根据 operation 的不同值，从而指令不同的操作
            switch (operation) {
                case Mips.ADD:
                    dst = src1 + src2;
                    break;
                case Mips.SUB:
                    dst = src1 - src2;
                    break;
                case Mips.MULT:
                    dst = src1 * src2;
                    registers[regLo] = (int) Lib.extract(dst, 0, 32);
                    registers[regHi] = (int) Lib.extract(dst, 32, 32);
                    break;
                case Mips.DIV:
                    try {
                        registers[regLo] = (int) (src1 / src2);
                        registers[regHi] = (int) (src1 % src2);
                        if (registers[regLo] * src2 + registers[regHi] != src1)
                            throw new ArithmeticException();
                    } catch (ArithmeticException e) {
                        throw new MipsException(exceptionOverflow);
                    }
                    break;

                case Mips.SLL:
                    dst = src2 << (src1 & 0x1F);
                    break;
                case Mips.SRA:
                    dst = src2 >> (src1 & 0x1F);
                    break;
                case Mips.SRL:
                    dst = src2 >>> (src1 & 0x1F);
                    break;

                case Mips.SLT:
                    dst = (src1 < src2) ? 1 : 0;
                    break;

                case Mips.AND:
                    dst = src1 & src2;
                    break;
                case Mips.OR:
                    dst = src1 | src2;
                    break;
                case Mips.NOR:
                    dst = ~(src1 | src2);
                    break;
                case Mips.XOR:
                    dst = src1 ^ src2;
                    break;
                case Mips.LUI:
                    dst = imm << 16;
                    break;

                case Mips.BEQ:
                    branch = (src1 == src2);
                    break;
                case Mips.BNE:
                    branch = (src1 != src2);
                    break;
                case Mips.BGEZ:
                    branch = (src1 >= 0);
                    break;
                case Mips.BGTZ:
                    branch = (src1 > 0);
                    break;
                case Mips.BLEZ:
                    branch = (src1 <= 0);
                    break;
                case Mips.BLTZ:
                    branch = (src1 < 0);
                    break;

                case Mips.JUMP:
                    break;

                case Mips.MFLO:
                    dst = registers[regLo];
                    break;
                case Mips.MFHI:
                    dst = registers[regHi];
                    break;
                case Mips.MTLO:
                    registers[regLo] = (int) src1;
                    break;
                case Mips.MTHI:
                    registers[regHi] = (int) src1;
                    break;

                case Mips.SYSCALL:
                    // 指令是系统调用，抛出异常
                    // 异常会在 UserProcess 被捕捉和处理
                    throw new MipsException(exceptionSyscall);

                case Mips.LOAD:
                    value = readMem(addr, size);

                    if (!test(Mips.UNSIGNED))
                        dst = Lib.extend(value, 0, size * 8);
                    else
                        dst = value;

                    break;

                case Mips.LWL:
                    value = readMem(addr & ~0x3, 4);

                    // LWL shifts the input left so the addressed byte is highest
                    preserved = (3 - (addr & 0x3)) * 8;    // number of bits to preserve
                    mask = -1 << preserved;        // preserved bits are 0 in mask
                    dst = value << preserved;    // shift input to correct place
                    addr &= ~0x3;

                    break;

                case Mips.LWR:
                    value = readMem(addr & ~0x3, 4);

                    // LWR shifts the input right so the addressed byte is lowest
                    preserved = (addr & 0x3) * 8;    // number of bits to preserve
                    mask = -1 >>> preserved;    // preserved bits are 0 in mask
                    dst = value >>> preserved;    // shift input to correct place
                    addr &= ~0x3;

                    break;

                case Mips.STORE:
                    writeMem(addr, size, (int) src2);
                    break;

                case Mips.SWL:
                    value = readMem(addr & ~0x3, 4);

                    // SWL shifts highest order byte into the addressed position
                    preserved = (3 - (addr & 0x3)) * 8;
                    mask = -1 >>> preserved;
                    dst = src2 >>> preserved;

                    // merge values
                    dst = (dst & mask) | (value & ~mask);

                    writeMem(addr & ~0x3, 4, (int) dst);
                    break;

                case Mips.SWR:
                    value = readMem(addr & ~0x3, 4);

                    // SWR shifts the lowest order byte into the addressed position
                    preserved = (addr & 0x3) * 8;
                    mask = -1 << preserved;
                    dst = src2 << preserved;

                    // merge values
                    dst = (dst & mask) | (value & ~mask);

                    writeMem(addr & ~0x3, 4, (int) dst);
                    break;

                case Mips.UNIMPL:
                    System.err.println("Warning: encountered unimplemented inst");

                case Mips.INVALID:
                    throw new MipsException(exceptionIllegalInstruction);

                default:
                    Lib.assertNotReached();
            }
        }

        private void writeBack() throws MipsException {
            // if instruction is signed, but carry bit !+ sign bit, throw
            if (test(Mips.OVERFLOW) && Lib.test(dst, 31) != Lib.test(dst, 32))
                throw new MipsException(exceptionOverflow);

            if (test(Mips.DELAYEDLOAD))
                delayedLoad(dstReg, (int) dst, mask);
            else
                finishLoad();

            if (test(Mips.LINK))
                dst = nextPC;

            if (test(Mips.DST) && dstReg != 0)
                registers[dstReg] = (int) dst;

            if ((test(Mips.DST) || test(Mips.DELAYEDLOAD)) && dstReg != 0) {
                if (Lib.test(dbgFullDisassemble)) {
                    System.out.print("#0x" + Lib.toHexString((int) dst));
                    if (test(Mips.DELAYEDLOAD))
                        System.out.print(" (delayed load)");
                }
            }

            if (test(Mips.BRANCH) && branch) {
                nextPC = jtarget;
            }

            advancePC(nextPC);

            if ((Lib.test(dbgDisassemble) && !Lib.test(dbgProcessor)) ||
                    Lib.test(dbgFullDisassemble))
                System.out.print("\n");
        }

        // state used to execute a single instruction
        int value, op, rs, rt, rd, sh, func, target, imm;
        int operation, format, flags;
        String name;

        int size;
        int addr, nextPC, jtarget, dstReg;
        long src1, src2, dst;
        int mask;
        boolean branch;
    }

    private static class Mips {
        Mips() {
        }

        Mips(int operation, String name) {
            this.operation = operation;
            this.name = name;
        }

        Mips(int operation, String name, int format, int flags) {
            this(operation, name);
            this.format = format;
            this.flags = flags;
        }

        int operation = INVALID;
        String name = "invalid ";
        int format;
        int flags;

        // operation types
        static final int
                INVALID = 0,
                UNIMPL = 1,
                ADD = 2,
                SUB = 3,
                MULT = 4,
                DIV = 5,
                SLL = 6,
                SRA = 7,
                SRL = 8,
                SLT = 9,
                AND = 10,
                OR = 11,
                NOR = 12,
                XOR = 13,
                LUI = 14,
                MFLO = 21,
                MFHI = 22,
                MTLO = 23,
                MTHI = 24,
                JUMP = 25,
                BEQ = 26,
                BNE = 27,
                BLEZ = 28,
                BGTZ = 29,
                BLTZ = 30,
                BGEZ = 31,
                SYSCALL = 32,
                LOAD = 33,
                LWL = 36,
                LWR = 37,
                STORE = 38,
                SWL = 39,
                SWR = 40,
                MAX = 40;

        static final int
                IFMT = 1,
                JFMT = 2,
                RFMT = 3;

        static final int
                DST = 0x00000001,
                DSTRA = 0x00000002,
                OVERFLOW = 0x00000004,
                SRC1SH = 0x00000008,
                SRC2IMM = 0x00000010,
                UNSIGNED = 0x00000020,
                LINK = 0x00000040,
                DELAYEDLOAD = 0x00000080,
                SIZEB = 0x00000100,
                SIZEH = 0x00000200,
                SIZEW = 0x00000400,
                BRANCH = 0x00000800;

        static final char
                RS = 's',
                RT = 't',
                RD = 'd',
                IMM = 'i',
                SHIFTAMOUNT = 'h',
                ADDR = 'a',    // imm(rs)
                TARGET = 'j',
                RETURNADDRESS = 'r';    // rd, or none if rd=31; can't be last

        static final Mips[] optable = {
                new Mips(),                        // special
                new Mips(),                        // reg-imm
                new Mips(JUMP, "j j", JFMT, BRANCH),
                new Mips(JUMP, "jal j", JFMT, BRANCH | LINK | DST | DSTRA),
                new Mips(BEQ, "beq stj", IFMT, BRANCH),
                new Mips(BNE, "bne stj", IFMT, BRANCH),
                new Mips(BLEZ, "blez sj", IFMT, BRANCH),
                new Mips(BGTZ, "bgtz sj", IFMT, BRANCH),
                new Mips(ADD, "addi tsi", IFMT, DST | SRC2IMM | OVERFLOW),
                new Mips(ADD, "addiu tsi", IFMT, DST | SRC2IMM),
                new Mips(SLT, "slti tsi", IFMT, DST | SRC2IMM),
                new Mips(SLT, "sltiu tsi", IFMT, DST | SRC2IMM | UNSIGNED),
                new Mips(AND, "andi tsi", IFMT, DST | SRC2IMM | UNSIGNED),
                new Mips(OR, "ori tsi", IFMT, DST | SRC2IMM | UNSIGNED),
                new Mips(XOR, "xori tsi", IFMT, DST | SRC2IMM | UNSIGNED),
                new Mips(LUI, "lui ti", IFMT, DST | SRC2IMM | UNSIGNED),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(BEQ, "beql stj", IFMT, BRANCH),
                new Mips(BNE, "bnel stj", IFMT, BRANCH),
                new Mips(BLEZ, "blezl sj", IFMT, BRANCH),
                new Mips(BGTZ, "bgtzl sj", IFMT, BRANCH),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(LOAD, "lb ta", IFMT, DELAYEDLOAD | SIZEB),
                new Mips(LOAD, "lh ta", IFMT, DELAYEDLOAD | SIZEH),
                new Mips(LWL, "lwl ta", IFMT, DELAYEDLOAD),
                new Mips(LOAD, "lw ta", IFMT, DELAYEDLOAD | SIZEW),
                new Mips(LOAD, "lbu ta", IFMT, DELAYEDLOAD | SIZEB | UNSIGNED),
                new Mips(LOAD, "lhu ta", IFMT, DELAYEDLOAD | SIZEH | UNSIGNED),
                new Mips(LWR, "lwr ta", IFMT, DELAYEDLOAD),
                new Mips(),
                new Mips(STORE, "sb ta", IFMT, SIZEB),
                new Mips(STORE, "sh ta", IFMT, SIZEH),
                new Mips(SWL, "swl ta", IFMT, 0),
                new Mips(STORE, "sw ta", IFMT, SIZEW),
                new Mips(),
                new Mips(),
                new Mips(SWR, "swr ta", IFMT, 0),
                new Mips(),
                new Mips(UNIMPL, "ll "),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(UNIMPL, "sc "),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
        };

        static final Mips[] specialtable = {
                new Mips(SLL, "sll dth", RFMT, DST | SRC1SH),
                new Mips(),
                new Mips(SRL, "srl dth", RFMT, DST | SRC1SH),
                new Mips(SRA, "sra dth", RFMT, DST | SRC1SH),
                new Mips(SLL, "sllv dts", RFMT, DST),
                new Mips(),
                new Mips(SRL, "srlv dts", RFMT, DST),
                new Mips(SRA, "srav dts", RFMT, DST),
                new Mips(JUMP, "jr s", RFMT, BRANCH),
                new Mips(JUMP, "jalr rs", RFMT, BRANCH | LINK | DST),
                new Mips(),
                new Mips(),
                new Mips(SYSCALL, "syscall "),
                new Mips(UNIMPL, "break "),
                new Mips(),
                new Mips(UNIMPL, "sync "),
                new Mips(MFHI, "mfhi d", RFMT, DST),
                new Mips(MTHI, "mthi s", RFMT, 0),
                new Mips(MFLO, "mflo d", RFMT, DST),
                new Mips(MTLO, "mtlo s", RFMT, 0),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(MULT, "mult st", RFMT, 0),
                new Mips(MULT, "multu st", RFMT, UNSIGNED),
                new Mips(DIV, "div st", RFMT, 0),
                new Mips(DIV, "divu st", RFMT, UNSIGNED),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(ADD, "add dst", RFMT, DST | OVERFLOW),
                new Mips(ADD, "addu dst", RFMT, DST),
                new Mips(SUB, "sub dst", RFMT, DST | OVERFLOW),
                new Mips(SUB, "subu dst", RFMT, DST),
                new Mips(AND, "and dst", RFMT, DST),
                new Mips(OR, "or dst", RFMT, DST),
                new Mips(XOR, "xor dst", RFMT, DST),
                new Mips(NOR, "nor dst", RFMT, DST),
                new Mips(),
                new Mips(),
                new Mips(SLT, "slt dst", RFMT, DST),
                new Mips(SLT, "sltu dst", RFMT, DST | UNSIGNED),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
        };

        static final Mips[] regimmtable = {
                new Mips(BLTZ, "bltz sj", IFMT, BRANCH),
                new Mips(BGEZ, "bgez sj", IFMT, BRANCH),
                new Mips(BLTZ, "bltzl sj", IFMT, BRANCH),
                new Mips(BGEZ, "bgezl sj", IFMT, BRANCH),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(BLTZ, "bltzal sj", IFMT, BRANCH | LINK | DST | DSTRA),
                new Mips(BGEZ, "bgezal sj", IFMT, BRANCH | LINK | DST | DSTRA),
                new Mips(BLTZ, "bltzlal sj", IFMT, BRANCH | LINK | DST | DSTRA),
                new Mips(BGEZ, "bgezlal sj", IFMT, BRANCH | LINK | DST | DSTRA),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips(),
                new Mips()
        };
    }
}
